#ifndef OPTFRAME_INITIALSOLUTIONPATTERNIMPROVEMENTPROXIMITY_HPP_
#define OPTFRAME_INITIALSOLUTIONPATTERNIMPROVEMENTPROXIMITY_HPP_

#include "../OptFrame/InitialSolution.h"
#include "../OptFrame/Util/TestSolution.hpp"

#include <algorithm>


class PRVPInitialSolutionPatternImprovementProximity: public InitialSolution<RepPRVP>
{
private:
	PRVPProblemInstance& pPRVP;
	RandGen& rg;
	Heuristic<RepPRVP, MemPRVP>& h;
	double static const inf = 9999999;

	vector<int> decompoeEscolha(int escolha)
	{
		vector<int> periodos;
		int p = pPRVP.nPeriod - 1;
		while (escolha != 0)
		{
			if (escolha % 2 == 1)
			{
				periodos.push_back(p);
			}
			escolha = escolha / 2;
			p--; //passando para o proximo periodo
		}

		return periodos;
	}

	double removeCliInRoute(int id, vector<vector<int> >& rt)
	{
		double custo;//custo da remoção do cliente
		for (unsigned int r = 0; r < rt.size(); r++)
			for (unsigned int c = 0; c < rt.at(r).size(); c++)
			{
				if (id == rt.at(r).at(c))
				{
					if (rt.at(r).size() == 1)//se tiver somente um elemento
					{
						custo = -(*pPRVP.dist)(0, rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), 0);
					}
					else
					{
						//retornando o custo da remoção desse cliente
						if (c == 0)
						{
							custo = (*pPRVP.dist)(0, rt.at(r).at(c + 1)) - (*pPRVP.dist)(0, rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), rt.at(r).at(c + 1));
						}
						else if (c == rt.at(r).size() - 1)
						{
							custo = (*pPRVP.dist)(rt.at(r).at(c - 1), 0) - (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), 0);
						}
						else
						{
							custo = (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c + 1)) - (*pPRVP.dist)(rt.at(r).at(c - 1), rt.at(r).at(c)) - (*pPRVP.dist)(rt.at(r).at(c), rt.at(r).at(c + 1));
						}
					}
					rt.at(r).erase(rt.at(r).begin() + c);
					return custo;
				}
			}
	}

	double removeCli(RepPRVP& rep, int c, ADS& ads)
	{
		double custo = 0;
		for (int i = 0; i < ads.getLocal_cli().at(c).size(); i++)
		{
			custo += removeCliInRoute(c, rep.at(ads.getLocal_cli().at(c).at(i)));
		}

		return custo;

	}

	double bestInsertion(vector<vector<int> > routes, int periodo, int cli, bestPos & pos, vector<double>& cap, double taxa)
	{
		//melhor valor de inserção
		double best_insert = inf;
		//melhor posicao de inserção
		pos.periodo = periodo;

		double aux_insert;

		//pegando a matriz de distancia
		Matrix<double>& dist = (*pPRVP.dist);

		/*cout<<dist<<endl;
		 exit(1);*/

		//verificando a melhor posição em todos os periodos
		for (int r = 0; r < routes.size(); r++)
		{
			if (routes.at(r).size() == 0)// se a rota estiver vazia
			{
				aux_insert = dist(0, cli) + dist(cli, 0);

				if (aux_insert < best_insert)
				{
					best_insert = aux_insert;
					pos.rota = r;
					pos.posicao = 0;
				}

			}
			else //caso a rota não estiver vazia
			{
				//verificando se ao adicionar o cliente a essa rota não estoura a capacidade do veículo
				if (cap.at(r) + pPRVP.dados->at(cli).at(DEMANDA) <= (pPRVP.capacidade * taxa))
				{
					//testando se a melhor posição fica entre o depósito e o primeiro cliente da rota "r"
					aux_insert = dist(0, cli) + dist(cli, routes.at(r).at(0)) - dist(0, routes.at(r).at(0));

					if (aux_insert < best_insert)
					{
						best_insert = aux_insert;
						pos.rota = r;
						pos.posicao = 0;
					}

					//testando para as demais posições
					for (int c = 0; c < routes.at(r).size() - 1; c++)
					{
						aux_insert = dist(routes.at(r).at(c), cli) + dist(cli, routes.at(r).at(c + 1)) - dist(routes.at(r).at(c), routes.at(r).at(c + 1));
						if (aux_insert < best_insert)
						{
							best_insert = aux_insert;
							pos.rota = r;
							pos.posicao = c + 1;
						}
					}
					//testando se a melhor posição fica entre o ultimo cliente da rota "r" e o depósito
					aux_insert = dist(routes.at(r).at(routes.at(r).size() - 1), cli) + dist(cli, 0) - dist(routes.at(r).at(routes.at(r).size() - 1), 0);
					if (aux_insert < best_insert)
					{
						best_insert = aux_insert;
						pos.rota = r;
						pos.posicao = routes.at(r).size();
					}
				}
			}
		}

		return best_insert;
	}

public:

	PRVPInitialSolutionPatternImprovementProximity(PRVPProblemInstance& _pPRVP, RandGen& _rg, Heuristic<RepPRVP, MemPRVP>& _h) :
		pPRVP(_pPRVP), rg(_rg), h(_h)
	{
	}

	virtual ~PRVPInitialSolutionPatternImprovementProximity()
	{
	}

	SolutionPRVP& generateSolution()
	{
		//criando a representação
		RepPRVP rep;
		//criando as rotas
		vector < vector<int> > routes(pPRVP.nVeic);
		//adicionando as rotas à represetação
		for (int i = 0; i < pPRVP.nPeriod; i++)
		{
			rep.push_back(routes);
		}
		//vetores para armazenar o valor da melhor inserção, e a posição da melhor inserção.
		vector<int> clients;

		//separando clientes por número de opções
		vector < vector<int> > cli_comb(pPRVP.nPeriod * 3);
		//randomizando a ordem dos clientes
		for (int c = 1; c <= pPRVP.nCli; c++)
		{
			cli_comb.at(pPRVP.dados->at(c).at(NCOMB) - 1).push_back(c);
		}
		//embaralhando os clientes
		for (int i = 0; i < cli_comb.size(); i++)
		{
			if (cli_comb.at(i).size() > 0)
				rg.shuffle(cli_comb.at(i));
		}
		//adicionando os clientes por ordem de menores opções.
		for (int i = 0; i < cli_comb.size(); i++)
		{
			for (int j = 0; j < cli_comb.at(i).size(); j++)
			{
				clients.push_back(cli_comb.at(i).at(j));
			}
		}

		for (int i = 0; i < clients.size(); i++)
		{
			//RepPRVP& rep = s.getR();
			int taxa = clients.size() * 0.2;
			if (i % taxa == 0)
			{
				TestSolution<RepPRVP> sol(rep);
				//cout<<endl<<"antes: "<<*rep<<endl;
				h.exec(sol, 20, 0);
				rep = sol.getR();
				//cout<<"depois: "<<*rep<<endl;
				//getchar();
				//delete sol;
			}

			vector < vector<double> > cap_utilizada;

			for (int p = 0; p < rep.size(); p++)
			{
				vector<double> aux;
				for (int r = 0; r < rep.at(p).size(); r++)
				{
					double cap = 0;
					for (int c = 0; c < rep.at(p).at(r).size(); c++)
					{
						cap += pPRVP.dados->at(rep.at(p).at(r).at(c)).at(DEMANDA);
					}
					aux.push_back(cap);
				}
				cap_utilizada.push_back(aux);
			}

			//double custoRemocao = removeCli(rep, clients.at(i), e.getM()); // removendo o cliente "c" da solução

			//estruturas auxiliares para cada combinação de periodos de cada cliente
			double eval_escolha = 0;
			vector<bestPos> pos_aux;

			double bestEval = inf;
			vector<bestPos> bestPosCli;

			double prob = 1.0;
			do
			{
				//para cada uma das combinações
				for (int escolha = 0; escolha < pPRVP.dados->at(clients.at(i)).at(NCOMB); escolha++)
				{
					eval_escolha = 0;
					pos_aux.clear();

					//decompondo a primeir escolha
					vector<int> periodos = decompoeEscolha(pPRVP.dados->at(clients.at(i)).at(NCOMB + escolha + 1));
					//para cada periodo decomposto
					//	fazer as inserções por periodo guardando os menores valores
					for (int p = 0; p < periodos.size(); ++p)
					{
						bestPos aux;

						eval_escolha += bestInsertion(rep.at(periodos.at(p)), periodos.at(p), clients.at(i), aux, cap_utilizada.at(periodos.at(p)), prob);
						pos_aux.push_back(aux);
					}

					if (eval_escolha < bestEval)
					{
						bestEval = eval_escolha;
						bestPosCli = pos_aux;
					}
				}

				prob += 0.1;
			} while (bestEval > inf - 10000);

			//inserindo o cliente na melhor posição em cada período
			for (int bpos = 0; bpos < bestPosCli.size(); bpos++)
			{

				int periodo = bestPosCli.at(bpos).periodo; //periodo
				int rota = bestPosCli.at(bpos).rota; // rota
				int posicao = bestPosCli.at(bpos).posicao; // posição de inserção

				//fazendo a inserção
				rep.at(periodo).at(rota).insert(rep.at(periodo).at(rota).begin() + posicao, clients.at(i));

			}

		}

#ifdef DEBUG
		bool found = false;
		vector<int> not_founds;
		for (int c = 1; c <= pPRVP.nCli; c++)
		{
			found = false;
			for (int p = 0; p < rep.size(); p++)
			{
				for (int r = 0; r < rep.at(p).size(); r++)
				{
					for (int cli = 0; cli < rep.at(p).at(r).size(); cli++)
					{
						if (rep.at(p).at(r).at(cli) == c)
						{
							found = true;
						}
					}
				}
			}
			if (!found)
			{
				cout<<"faltou cliente : "<<c<<endl;
				//cout<<rep<<endl;
				//exit(1);
				not_founds.push_back(c);
			}
		}

		//se algum cliente ficou sem ser adicionado
		if (not_founds.size() > 0)
		{
			for (int i = 0; i < not_founds.size(); i++)
			{
				//escolha aleatoria
				int comb = rg.rand() % pPRVP.dados->at(not_founds.at(i)).at(NCOMB);
				vector<int> periodos = decompoeEscolha(comb);

				for (int p = 0; p < periodos.size(); ++p)
				{
					int rota = rg.rand() % rep.at(periodos.at(p)).size();
					rep.at(periodos.at(p)).at(rota).push_back(not_founds.at(i));
				}
			}
		}

#endif
		return *new TestSolution<RepPRVP> (rep);

	}

};

#endif /*OPTFRAME_INITIALSOLUTIONPATTERNIMPROVEMENTPROXIMITY_HPP_*/
